	<!DOCTYPE html>
<html lang="zh-Hans">
	<head>
		<!--[if lt IE 9]>
        	<style>body {display: none; background: none !important} </style>
        	<meta http-equiv="Refresh" Content="0; url=//outdatedbrowser.com/" />
    	<![endif]-->

		<meta charset="utf-8">
		<meta http-equiv="X-UA-Compatible" content="IE=edge, chrome=1" />
		<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">
		<meta name="format-detection" content="telephone=no" />
		<meta name="author" content="Shawn" />
		

		<link rel="apple-touch-icon" href="http://og6esej9r.bkt.clouddn.com/me-0.JPG">
		<link rel="alternate" href="/atom.xml" title="诗酒趁年华" type="application/atom+xml">
		<link rel="shortcut icon" href="/img/me.JPG">
		<link href="//cdn.bootcss.com/animate.css/3.5.1/animate.min.css" rel="stylesheet">
		<link href="//cdn.bootcss.com/fancybox/2.1.5/jquery.fancybox.min.css" rel="stylesheet">
		<script src="//cdn.bootcss.com/pace/1.0.2/pace.min.js"></script>
    	<link href="//cdn.bootcss.com/pace/1.0.2/themes/blue/pace-theme-loading-bar.css" rel="stylesheet">
		<link rel="stylesheet" href="/css/style.css">
		
		

		<link href="//cdn.bootcss.com/font-awesome/4.6.3/css/font-awesome.min.css" rel="stylesheet">
		
		<title>算法设计与分析——突破O(m)时间复杂度限制的无向图动态深度优先算法 | 诗酒趁年华</title>

		<script src="//cdn.bootcss.com/jquery/2.2.4/jquery.min.js"></script>
		<script src="//cdn.bootcss.com/clipboard.js/1.5.10/clipboard.min.js"></script>
		<!--<script src="/js/huaji.js"></script>-->
		
		<script src="/js/APlayer.min.js"></script>
		<script src="/js/canvas.js"></script>
  		<script src="/js/leftmusic.js"></script>
  		<script src="/js/jquery.marquee.min.js"></script>
  		<script src="//code.jquery.com/jquery-migrate-1.2.1.min.js"></script>
		
		 
		<!-- Live2D Library -->
        <script src="/js/live2d.min.js"></script>        
        <!-- Live2D Framework -->
        <script src="/js/Live2DFramework.js"></script>
        <!-- User's Script -->
    	<script src="/js/utils/MatrixStack.js"></script>
        <script src="/js/utils/ModelSettingJson.js"></script>
        <script src="/js/PlatformManager.js"></script>
        <script src="/js/LAppDefine.js"></script>
        <script src="/js/LAppModel.js"></script>
        <script src="/js/LAppLive2DManager.js"></script>
        <script src="/js/22.js"></script>	
         		        
	
		<script>
  			var yiliaConfig = {
     	   		fancybox: true,
        		animate: true,
        		isHome: false,
        		isPost: true,
        		isArchive: false,
        		isTag: false,
        		isCategory: false,
        		fancybox_js: "//cdn.bootcss.com/fancybox/2.1.5/jquery.fancybox.min.js",
        		scrollreveal: "//cdn.bootcss.com/scrollReveal.js/3.1.4/scrollreveal.min.js",
        		search: true
    		}
		</script>
		
		
		
		<script>
        	yiliaConfig.jquery_ui = [true, "//cdn.bootcss.com/jqueryui/1.10.4/jquery-ui.min.js", "//cdn.bootcss.com/jqueryui/1.10.4/css/jquery-ui.min.css"];
    	</script>
		

		<script> yiliaConfig.rootUrl = "\/";</script>	
		

		
	</head>

	 
		<body onload="ThisIs22()">
	
  		<div id="container">
    		<div class="left-col">
    			<div class="overlay"></div>
    			<div class="intrude-less">
	    			<header id="header" class="inner">
            			<a href="/" class="profilepic">
                			<img src="/img/me.JPG" class="animated zoomIn">
            			</a>
            			<hgroup>
              				<h1 class="header-author" style="width:100%"><a href="/">Shawn</a></h1>
            			</hgroup>
            			<p class="header-subtitle">一个喜欢捣鼓前端的产品汪。<br/>总字数：<span class="post-count" style="font-weight: bold;font-family: Arial, Helvetica, "宋体";color: black;">17.8k</span></p>

            			<form id="search-form"> <!-- 搜索框相关 -->
    			    		<input type="text" id="local-search-input" name="q" results="0" placeholder="" class="search form-control" autocomplete="off" autocorrect="off"/>
   				    		<i class="fa fa-times" onclick="resetSearch()"></i> <!-- 清空/重置搜索框 -->
			    		</form>
			    		<div id="local-search-result"></div> <!-- 搜索结果区 -->
			    		<p class='no-result'>啊哦。。。<br/>没有符合条件的文章。。。<br/>∠( ᐛ 」∠)＿</p> <!-- 无匹配时显示，注意请在 CSS 中设置默认隐藏 -->
            			
            			<div id="switch-area" class="switch-area">
    			            <div class="switch-wrap">
    			                <section class="switch-part switch-part1">
    			                    <nav class="header-menu">
    			                    	<a href="/" title="回到首页"><i class="fa fa-home"></i></a>
    			                    	<a href="/archives/" title="文章归档"><i class="fa fa-archives"></i></a>
    			                    	<a href="/tags/" title="标签/分类"><i class="fa fa-tags"></i></a>
    			                    	<a href="/photoes/" title="照片/壁纸"><i class="fa fa-photo"></i></a>
    			                    	<a href="/friends/" title="友情链接"><i class="fa fa-links"></i></a>
    			                    	<a href="/about/" title="关于我/留言板"><i class="fa fa-about"></i></a>
    			                    	<a href="/download/" title="相关下载"><i class="fa fa-download"></i></a>
    									<a class="set-view-mode" href="javascript:void(0)" title="夜间模式"><i class="fa fa-moon-o"></i></a>
    			                    </nav>
    			                </section>   
    			                <section class="switch-part switch-part2">
    			                    <div class="widget tagcloud" id="js-tagcloud">
    			                        <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/2017/">2017</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/CDN/">CDN</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/DFS/">DFS</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Github/">Github</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/HTML5/">HTML5</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Hexo/">Hexo</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/JavaScript/">JavaScript</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/PS/">PS</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/SSL/">SSL</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/flag/">flag</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/https/">https</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/localStorage/">localStorage</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/nginx/">nginx</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/sessionStorage/">sessionStorage</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/夜间模式/">夜间模式</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/影评/">影评</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/文档/">文档</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/服务学/">服务学</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/编译原理/">编译原理</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/随笔/">随笔</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/项目管理/">项目管理</a></li></ul>
    			                    </div>
    			                </section>
    			                
    			                            
 			            	</div>
 			            	<div class="marquee"><script type="text/javascript" src="https://api.lwl12.com/hitokoto/main/get?encode=js&charset=utf-8"></script><div id="lwlhitokoto"><script>lwlhitokoto()</script></div></div><script>$('.marquee').marquee();</script>
    			        </div>
    			    </header>   
    			</div>
    			       
    		</div>
    		 
    			<script src="//cdn.bootcss.com/jqueryui/1.10.4/jquery-ui.min.js"></script>
    			<script src="/js/move.js"></script>
    			<div id="movediv"> 
        			<canvas id="glcanvas" width="170" height="200"> <button id="btnChange" class="active" style="visibility:hidden;width=10px!important;">C</button></canvas>
    			</div>
    		
    		<div class="xm"><img src="/img/xm.png"></div>
    		<div class="mid-col">
    			<nav id="mobile-nav">
      <div class="overlay">
          <div class="slider-trigger"></div>
          <h1 class="header-author js-mobile-header hide"><a href="/" title="回到主页">Shawn</a></h1>
      </div>
    <div class="intrude-less">
        <header id="header" class="inner">
            <a href="/" class="profilepic">
                <img src="/img/me.JPG" class="animated zoomIn">
            </a>
            <hgroup>
              <h1 class="header-author"><a href="/" title="回到主页">Shawn</a></h1>
            </hgroup>
            
            <p class="header-subtitle"><span class="post-count">一个喜欢捣鼓前端的产品汪。<br/>总字数：17.8k</span></p>
            
            <nav class="header-menu">
            	<div>
    			<a href="/" title="回到首页"><i class="fa fa-home"></i></a>
    			<a href="/archives/" title="文章归档"><i class="fa fa-archives"></i></a>
    			<a href="/tags/" title="标签/分类"><i class="fa fa-tags"></i></a>
    			<a href="/photoes/" title="照片/壁纸"><i class="fa fa-photo"></i></a>
    			<a href="/friends/" title="友情链接"><i class="fa fa-links"></i></a>
    			</div>
    			<div>
    			<a href="/about/" title="关于我/留言板"><i class="fa fa-about"></i></a>
    			<a href="/download/" title="相关下载"><i class="fa fa-download"></i></a>
    			<a class="set-view-mode" href="javascript:void(0)" title="夜间模式"><i class="fa fa-moon-o"></i></a>
    			</div>
    		</nav><br/><br/><br/>
        </header>                
    </div>
    <link class="menu-list" tags="标签" friends="友情链接" about="关于我"/>
</nav>
      			<div class="body-wrap"><article id="post-Algorithm-homework" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/2017/01/10/Algorithm-homework/" class="article-date">
      <time datetime="2017-01-10T06:30:48.000Z" itemprop="datePublished">2017-01-10</time>
</a>


    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      		算法设计与分析——突破O(m)时间复杂度限制的无向图动态深度优先算法
    </h1>
  

      </header>
      
      <div class="article-info article-info-post">
        
    <div class="article-category tagcloud">
    <a class="article-category-link" href="/categories/算法/">算法</a>
    </div>


        
    <div class="article-tag tagcloud">
        <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/DFS/">DFS</a></li></ul>
    </div>

        <div class="clearfix"></div>
      </div>
      
    
    <div class="article-entry" itemprop="articleBody">
      
          
        <p><style><br>    table{width:90%;margin:0 auto;};<br></style><br>算法设计与分析课程论文，虽然写到最后也没看明白那论文写的是啥……</p>
<hr>
<p style="text-align:right">SODA 2016, Dynamic DFS in Undirected Graphs: breaking the O(m) barrier</p>

<h2 id="论文概述"><a href="#论文概述" class="headerlink" title="论文概述"></a>论文概述</h2><h3 id="文章概要"><a href="#文章概要" class="headerlink" title="文章概要"></a>文章概要</h3><p><span style="padding-left:2em;"></span>本文主要解决了无向图的动态遍历问题，使用动态深度优先搜索算法解决此问题。深度优先搜索算法（$DFS, Depth\ First\ Search$）是一种著名的图的遍历算法，在许多基本的图论问题中起到了至关重要的作用。本文简单的介绍了$DFS$树的相关知识，并详细的给出了动态$DFS$的算法，通过静态$DFS$、动态$DFS$算法的对比证明了动态$DFS$的正确性，展现了动态$DFS$的优越性。<br><a id="more"></a></p>
<h3 id="问题定义及算法要求"><a href="#问题定义及算法要求" class="headerlink" title="问题定义及算法要求"></a>问题定义及算法要求</h3><p><span style="padding-left:2em;"></span>定义一个无向图$G=(V,E)$，有$n=\mid V\ \mid$个结点和$m=\mid E\ \mid$条边。$G$的$DFS$遍历可从任意的$r\in V$作为根结点开始。进行一次$DFS$并生成一个$DFS$树的时间复杂度为$O(m+n)$。当我们在做$DFS$遍历的时候，当访问到一个节点时，会出现四种情况：</p>
<ol>
<li>此节点未被访问过，则此次的访问关系边（发起点$\rightarrow$接受点）称为树边（$tree\ edge$）；</li>
<li>此节点被访问过但此节点的子孙还没访问完，换句话说，此次的发起点的源头可以追溯到接收点，则此次访问关系边称为后向边（$back\ edge$）；</li>
<li>此节点被访问过且此节点的子孙已经访问完，而且发起点是搜索初始边，则称为前向边（$down\ edge$）；</li>
<li>此节点被访问过且此节点的子孙已经访问完，而且发起点不是搜索初始边，则称为横叉边（$cross\ edge$）。  </li>
</ol>
<p><span style="padding-left:2em;"></span>其实这种分类只是相对的，也会随着$DFS$的改变而改变，比如搜索入口、搜索顺序等。而一个生成树是一个$DFS$树的充要条件是每条非树边（$non-tree\ edge$）都是后向边（$back\ edge$）。因此我们可以看出对于任何给出的无向图，可能会有多种生成的$DFS$树。但是如果该图的遍历是按照邻接表的指定顺序来的话，最终的$DFS$树将会是唯一的。而有序$DFS$树的问题是在遍历严格按照邻接表的顺序的时候计算哪个结点应该被访问。<br><span style="padding-left:2em;"></span>大部分图论在现实世界中的应用需要处理随时间不断变化的图，这些变化通常表现在结点或边的增加或删除，所以一个图论的算法问题经常会在动态的环境下建模。也就是说，当图有了一系列改动之后，我们需要改动问题的解决方案。特别地，更新这个图论问题的解决方案的时间必须要比最好的静态算法的时间还要少。另外，还有一个更加严格的要求，就是这个动态的环境要是一个容错的环境。这样就能够面对一个给定的问题可以弹性的面对结点或边的错误并给出相关错误的解决方案。<br><span style="padding-left:2em;"></span>当一个动态的图论算法既能够处理插入也能够处理删除的时候，我们称它为完全动态的。当它只能够处理插入操作或只能处理删除操作的时候，我们称它为部分动态的，在这篇论文中的动态$DFS$算法则是完全动态的，可以在任何动态环境下使用。</p>
<h3 id="算法介绍"><a href="#算法介绍" class="headerlink" title="算法介绍"></a>算法介绍</h3><h4 id="准备工作"><a href="#准备工作" class="headerlink" title="准备工作"></a>准备工作</h4><p><span style="padding-left:2em;"></span>令$U$为指定的更新。在一开始，我们在给出的图上添加一个虚拟的结点$r$并把它和所有其他结点相连。本算法以任意的以$r$为根的$DFS$树开始，我们可以很容易的观察到，每个结点$r$的子节点为根的子树也是一个$DFS$树，是图$G+U$中相连的一部分。以下这些函数将会在后面用到：</p>
<ul>
<li>$T(x)$：$T$在结点$x$处的子树</li>
<li>$path(x,y)$：$T$中从结点$x$到结点$y$的路径</li>
<li>$dist_T(x,y)$：$T$中从结点$x$到结点$y$的路径经过的边数</li>
<li>$LCA(x,y)$：结点$x$和结点$y$的最近的共同祖先</li>
<li>$N(w)$：结点$w$在图$G+U$中的邻接表</li>
<li>$L(w)$：结点$w$在图$G+U$中的简化邻接表</li>
<li>$T^*$：由本文的算法计算出的$G+U$的以$r$为根的$DFS$树</li>
<li>$par(w)$：结点$w$在树$T^*$中的父节点</li>
</ul>
<p><span style="padding-left:2em;"></span>如果一个子树$T’$的根结点$r’$是路径$p$上的结点的子节点且$r’$不在路径$p$上，我们则称子树$T’$挂在路径$p$上。除非另外标注，否则每个路径的引用指的是采用如下定义的父子路径：如果一个在$DFS$树$T$上的路径$p$的端点在$T$中存在父子关系，那么它被称为是一条父子路径。<br><span style="padding-left:2em;"></span>接下来我们先说明一下由数据结构$D$(具体的定义在后面)支持的操作，用一些结点和边的删除操作（不包含插入操作）构成$U$。对$\forall w,x,y\in T$, 如果$path(x,y)$是$T$中的一条父子路径，那么以下两种查询方式通过使用数据结构$D$可以在$O(log^3n)$时间获得答案。</p>
<ol>
<li>$Query(w,x,y)$：在所有从$w$延伸出来的附在图$G+U$上的$path(x,y)$的边中，返回$path(x,y)$中距离$x$最近的边；</li>
<li>$Query(T(w),x,y)$：在所有在$T(w)$上的附在图$G+U$上的$path(x,y)$的边中，返回$path(x,y)$中距离$x$最近的边。</li>
</ol>
<h4 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h4><p><span style="padding-left:2em;"></span>$DFS$遍历有着如下的灵活性：当遍历到达某一结点时，输出$v$，下一个要遍历的结点可以是任何没有被访问过的$v$的邻居结点。为了高效的计算出$G+U$的$DFS$，我们的算法利用了这一灵活性、起始的$DFS$树$T$和下面的$DFS$遍历的特性。下面的图1中，边$e’_1$和$e’_2$在$DFS$遍历过程中可以忽略。在此补充个定理：令$T^{*}$为部分动态的$DFS$树，$v$为刚刚访问的结点，令$C$为子图中由未访问结点构成的与之相连的部分。设边$e$和$e’$分别为由树$T^{*}$中结点$v$和结点$v$的祖先$w$引出的边，那么我们就有了充分的理由认为在$DFS$遍历的剩余部分中，边$e’$不用被在意。（在$DFS$遍历过程中跳过$e’$是正确的，因为$e’$会在结果的$DFS$树中以回退边的形式存在）</p>
<div style="text-align:center;"><img src="http://pictures.shawnzeng.com/Algorithmhomework-01.png" alt="图1" width="60%"><p>图1</p></div>

<h4 id="不相交树分割法-Partition-T-U"><a href="#不相交树分割法-Partition-T-U" class="headerlink" title="不相交树分割法$Partition(T,U)$"></a>不相交树分割法$Partition(T,U)$</h4><p><span style="padding-left:2em;"></span>我们在此定义一个不相交分割树的方法，将会在后文中用到：<br><span style="padding-left:2em;"></span>对于一个给定的无向图$G$的$DFS$树$T$和一个有着错误结点和边的集合$U$，令$A$为$G+U$中的一个结点，则不相交分割树发就是通过$A$将树$T$划分为它的子图，分别为：</p>
<ol>
<li>一个路径的集合$P$，如图$(i)$，它其中的每条路径都是$T$中的一条父子路径并且不包含任何被删除的边或结点，且$(ii)$中$\mid\ P\mid\leq\mid U\ \mid$</li>
<li>一系列树的集合$T$，对于每个$t\in T$，都是$T$的子树，并且不包含任何被删除的边或结点。</li>
</ol>
<p><span style="padding-left:2em;"></span>另外，学要注意的是，对于任意$t_1,t_2\in T$,$t_1$和$t_2$之间不会有边，因为$T$是一个$DFS$树。</p>
<p><span style="padding-left:2em;"></span>不相交树分割法可对集合$A=V$ \ $\lbrace r\rbrace$进行如下操作：令$V_f$和$E_f$分别表示更新操作中$U$的错误的结点和边的集合，初始化$P=\Phi$，$T=\lbrace T(w)\mid w$是$r$的子节点$\rbrace$。对于每个结点$v\in V_f$，我们再分割过程中会有以下两种不同的处理方式：</p>
<ul>
<li>如果$v$在某个$T’\in T$，我们将从$par(v)$到$T’$根节点的路径添加到$P$中，并将$T’$从$T$中移出，并将从这条路径到$T$的所有子树添加上去；</li>
<li>如果$v$在某个$p\in P$，我们将$p$以$v$点为分割点，分割成两条路径，将$p$从$P$中移出并将这两条路径添加到$P$中。</li>
</ul>
<p><span style="padding-left:2em;"></span>对于边的删除，我们作以下处理：首先将在$T$中没有出现过的边从$E_f$中移出，接下来处理$E_f$中剩余边的过程就和处理上面已经描述过的$V_f$很相似了。对于每个边$e\in E_f$，只需要删除一个虚幻的包含着边中点的边计科，对于任意$v\in V_f$和$e\in E_f$，其时间复杂度为$O(n)$。</p>
<div style="text-align:center;"><img src="http://pictures.shawnzeng.com/Algorithmhomework-02.png" width="70%" alt="图2"><p>图2</p></div>

<h4 id="算法执行"><a href="#算法执行" class="headerlink" title="算法执行"></a>算法执行</h4><p><span style="padding-left:2em;"></span>现在，我们对算法已经有了大概的了解，接下来就是具体的执行过程了。首先将$U$中所有错误的边从数据结构$D$中删除，这样我们就可以使用不相交树分割法$partition(T,P)$，对于这其中所有未被访问的结点，都可以使用如下几个函数：</p>
<ul>
<li>$INFO(u):$如果$u$属于一棵树那么就返回$tree$，否则返回$path$；</li>
<li>$ISROOT(v):$如果$v$是$T$中一棵树的根节点，则将它设为$True$，否则设置为$False$；</li>
<li>$PATHPARAM(v):$如果$v$属于某些路径，输出$path(x,y)$，然后此变量存储$pair(x,y)$的值，否则为$null$。</li>
</ul>
<h4 id="静态-DFS-、动态-DFS-算法伪代码"><a href="#静态-DFS-、动态-DFS-算法伪代码" class="headerlink" title="静态$DFS$、动态$DFS$算法伪代码"></a>静态$DFS$、动态$DFS$算法伪代码</h4><blockquote>
<p>$\mathbf P\mathbf r\mathbf o\mathbf c\mathbf e\mathbf d\mathbf u\mathbf r\mathbf e\ Static-DFS(G,r):$计算以$r$为根结点的图$G$的$DFS$树的静态算法<br>&nbsp;&nbsp;1 $Stack\ S\leftarrow \Phi;$<br>&nbsp;&nbsp;2 $Push(r);$<br>&nbsp;&nbsp;3 $status(r)\leftarrow visited;$<br>&nbsp;&nbsp;4 while$\ S\neq empty$ do<br>&nbsp;&nbsp;5 <span style="padding-left:1em;"></span>$w\leftarrow Top(S);$<br>&nbsp;&nbsp;6 <span style="padding-left:1em;"></span>if $\ N(w)=\Phi\ $then$\ Pop(w);$<br>&nbsp;&nbsp;7 <span style="padding-left:1em;"></span>else<br>&nbsp;&nbsp;8 <span style="padding-left:2em;"></span>$u\leftarrow First\ vertex\ in\ N(w);$<br>&nbsp;&nbsp;9 <span style="padding-left:2em;"></span>$Remove\ u\ from\ N(w);$<br>10 <span style="padding-left:2em;"></span>if$\ status(u)=unvisited\ $then<br>11 <span style="padding-left:3em;"></span>$par(u)\leftarrow w;$<br>12 <span style="padding-left:3em;"></span>$status(u)\leftarrow visited;$<br>13 <span style="padding-left:3em;"></span>$Push(u);$<br>14 <span style="padding-left:2em;"></span>end<br>15 <span style="padding-left:1em;"></span>end<br>16 end</p>
</blockquote>
<p></p><p style="text-align:center">静态DFS算法</p><br>&nbsp;<p></p>
<blockquote>
<p>$\mathbf P\mathbf r\mathbf o\mathbf c\mathbf e\mathbf d\mathbf u\mathbf r\mathbf e\ Dynamic-DFS(G,U,r):$用来更新以$r$为根结点的图$G+U$的$DFS$树的动态算法<br>&nbsp;&nbsp;1 $Stack\ S\leftarrow \Phi;\color{grey}{(T,P)\leftarrow Partition(T,U);}$<br>&nbsp;&nbsp;2 $Push(r);$<br>&nbsp;&nbsp;3 $status(r)\leftarrow visited;\color{grey}{L(r)\leftarrow N(r);}$<br>&nbsp;&nbsp;4 while$\ S\neq empty$ do<br>&nbsp;&nbsp;5 <span style="padding-left:1em;"></span>$w\leftarrow Top(S);\color{grey}{u_0\leftarrow w}$<br>&nbsp;&nbsp;6 <span style="padding-left:1em;"></span>if $\ N(w)=\Phi\ $then$\ Pop(w);$<br>&nbsp;&nbsp;7 <span style="padding-left:1em;"></span>else<br>&nbsp;&nbsp;8 <span style="padding-left:2em;"></span>$u\leftarrow First\ vertex\ in\ N(w);$<br>&nbsp;&nbsp;9 <span style="padding-left:2em;"></span>$Remove\ u\ from\ N(w);$<br>10 <span style="padding-left:2em;"></span>if$\ status(u)=unvisited\ $then<br>11 <span style="padding-left:3em;"></span><font color="grey">if</font>$\color{grey}{\ INFO(u)=tree\ }$<font color="grey">then</font><br>12 <span style="padding-left:4em;"></span>$\color{grey}{\lbrace u_1,…,u_t\rbrace\leftarrow\ DFS-in-Tree;}$<br>13 <span style="padding-left:3em;"></span><font color="grey">else if</font>$\color{grey}{\ INFO(u)=path\ }$<font color="grey">then</font><br>14 <span style="padding-left:4em;"></span>$\color{grey}{\lbrace u_1,…,u_t\rbrace\leftarrow\ DFS-in-Path;}$<br>15 <span style="padding-left:3em;"></span><font color="grey">then</font><br>16 <span style="padding-left:3em;"></span><font color="grey">for</font>$\color{grey}{\ i=1\ to\ t\ }$<font color="grey">do</font><br>17 <span style="padding-left:4em;"></span>$par(u)\leftarrow w;$<br>18 <span style="padding-left:4em;"></span>$status(u)\leftarrow visited;$<br>19 <span style="padding-left:4em;"></span>$Push(u);$<br>20 <span style="padding-left:3em;"></span><font color="grey">end</font><br>21 <span style="padding-left:2em;"></span>end<br>22 <span style="padding-left:1em;"></span>end<br>23 end</p>
</blockquote>
<p></p><p style="text-align:center">动态DFS算法</p><br>&nbsp;<br><span style="padding-left:2em;"></span>对于每个结点$v$，$status(v)$被初始化为$unvisited$，且$L(v)$初始化为$\Phi$。首先，基于更新$U$通过不相交树分割法计算$DFS$树，在动态$DFS$处理过程中插入根节点$r$到栈$S$中。此时，当栈非空时，这个处理过程会重复以下操作:从栈顶读出最上层的结点，令这个结点为$w$，如果$L(w)$为空则将$w$弹出，否则令$u$为$L(w)$的第一个结点，如果结点$u$直到现在仍然未被访问，则看$u\in T$还是$u\in P$来决定是执行$DFS-in-Tree$还是$DFS-in-Path$。接着，动态$DFS$搜索会获得一条路$p_0$，$p_0$满足其上的每个结点的父节点都被标记为访问过，这条路径会被压到栈中，此算法会随着栈的更新继续迭代。<p></p>
<h3 id="时间复杂度分析"><a href="#时间复杂度分析" class="headerlink" title="时间复杂度分析"></a>时间复杂度分析</h3><p><span style="padding-left:2em;"></span>正如先前所讲的，不相交树分割法在算法的有效性中起到了关键的作用。它使我们能够限制算法中建立的简化邻接表$L$的大小。本算法通过在简化邻接表$L$上进行一次$DFS$遍历计算得到$T^{*}$，因此，包含计算$L$的时间在内，本算法的时间复杂度为$O(n+\mid L\mid)$。<br><span style="padding-left:2em;"></span>首先，给$L$的大小确立一个界限。在算法的每一步中，从$v_s\in P\cup T$中取出一条路径并将它加到$T^{*}$中。令$P_t$和$P_p$分别表示原属于$T$中的树和$P$中的路径的路径集合。对于每条路径$p_0\in P_t\cup P_p$，本算法会进行如下查询：</p>
<ol>
<li>对于$p_0$中的每个结点$w$，查询$P$中每条边在结点$w$上发生的事件，因此总的将边加到$L$的查询的时间复杂度为$O(n\mid P\mid)$；</li>
<li>如果$p_0$属于$P_p$，则查询从每个$t\in T$的边。由路径分半技术可以得出每条$P$中的路径在某条边从$P$中取出后将会减至一半，因此$P_p$的界限为$\mid P\mid log n$；</li>
<li>如果$p_0$属于$P_t$，则查询$p_0$下的子树的边。需要注意的是，这些字数会被添加到集合$T$中，因此需要查询的树的总数的界限将会由插入到$T$中的树的数量决定。每个子树仅仅可以添加到$T$中一次，所以本算法这部分的时间复杂度为O(n)。</li>
</ol>
<p><span style="padding-left:2em;"></span>所以，$L$的大小所决定的时间复杂度为$O(n(1+\mid P\mid)logn)$，又因为每条添加到$L$中的边所需的查询时间为$O(log^3n)$，所以总的查询时间为$O(n(1+\mid P\mid logn)log^3n)$。</p>
<h2 id="论文综述"><a href="#论文综述" class="headerlink" title="论文综述"></a>论文综述</h2><h3 id="问题领域及分类"><a href="#问题领域及分类" class="headerlink" title="问题领域及分类"></a>问题领域及分类</h3><p><span style="padding-left:2em;"></span>这篇文章主要讨论的问题领域为图的搜索，图搜索策略可看作一种在图中寻找路径的方法，而根据搜索策略的不同，图搜索算法一般分为两大类：盲目搜索和启发式搜索。顾名思义，盲目搜索是一种无向导的搜索，穷举所有可能的状态，这种算法实现简单，但效率很低；启发式搜索是根据具体的问题，在搜索的过程中产生启发性的信息，指导搜索过程，启发式搜索能极大提高搜索效率，并且有可能得到问题的最优解。<br><span style="padding-left:2em;"></span>之所以有这样的搜索策略的区分，是因为启发式搜索算法的每一步都是土向着目标状态进行搜索，而盲目搜索算法则是每一步按照固定的规则进行搜索，然后判断是否达到目标状态，从而产生了不同的搜索策略。常见的盲目搜索算法，以广度优先算法和深度优先算法为例，而启发式搜索，则以$A^*$算法为例。总而言之，搜索策略可以直观的表示如下：</p>
<ul>
<li>盲目搜索<ul>
<li>深度优先算法($DFS$)</li>
<li>广度优先算法($BFS$)</li>
</ul>
</li>
<li>启发式搜索<ul>
<li>$A^*$算法</li>
</ul>
</li>
</ul>
<p><span style="padding-left:2em;"></span>接下来开始介绍以上算法。</p>
<h3 id="深度优先算法-DFS"><a href="#深度优先算法-DFS" class="headerlink" title="深度优先算法($DFS$)"></a>深度优先算法($DFS$)</h3><h4 id="算法思想"><a href="#算法思想" class="headerlink" title="算法思想"></a>算法思想</h4><p><span style="padding-left:2em;"></span>从图中某个顶点$v$开始，访问此节点，然后依次从$v$未被访问的邻接点中出发深度优先遍历图，直到图中上所有和$v$有路径相通的顶点都被访问；若此时图中尚有顶点未被访问，则另选图中一个未被访问顶点做起点，重复以上过程，直到图中所有顶点都被访问为止。<br><span style="padding-left:2em;"></span>深度优先搜索遍历类似于树的先序遍历。假定给定图$G$的初态是所有顶点均未被访问过，在$G$中任选一个顶点$i$作为遍历的初始点，则深度优先搜索遍历可定义如下：</p>
<ol>
<li>首先访问顶点$i$，并将其访问标记置为访问过，即$visited[i]=1$；</li>
<li>然后搜索与顶点$i$有边相连的下一个顶点$j$，若$j$未被访问过，则访问它，并将$j$的访问标记置为访问过，$visited[j]=1$，然后从$j$开始重复此过程，若$j$已访问，再看与$i$有边相连的其它顶点；</li>
<li>若与$i$有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，直到图中所有顶点都被访问完止。</li>
</ol>
<h4 id="适用范围"><a href="#适用范围" class="headerlink" title="适用范围"></a>适用范围</h4><p><span style="padding-left:2em;"></span>需要有顺序遍历图，且找到一个解后输出即可。如：$trie$树排序。多用于只要求解，并且解答树中的重复节点较多并且重复较难判断时使用。</p>
<h4 id="举例"><a href="#举例" class="headerlink" title="举例"></a>举例</h4><p><span style="padding-left:2em;"></span>数独求解。给出一个不完整的数独，让填充其中空白的数字。</p>
<h3 id="广度优先算法-BFS"><a href="#广度优先算法-BFS" class="headerlink" title="广度优先算法($BFS$)"></a>广度优先算法($BFS$)</h3><h4 id="算法思想-1"><a href="#算法思想-1" class="headerlink" title="算法思想"></a>算法思想</h4><p><span style="padding-left:2em;"></span>广度优先搜索遍历类似于树的按层次遍历。设图$G$的初态是所有顶点均未访问，在$G$任选一顶点$i$作为初始点，则广度优先搜索的基本思想是：</p>
<ol>
<li>首先访问顶点$i$，并将其访问标志置为已被访问，即$visited[i]=1$；</li>
<li>接着依次访问与顶点$i$有边相连的所有顶点$w_1,w_2,…,w_t$；</li>
<li>然后再按顺序访问与$w_1,w_2,…,w_t$有边相连又未曾访问过的顶点；</li>
</ol>
<p><span style="padding-left:2em;"></span>依此类推，直到图中所有顶点都被访问完为止。</p>
<h4 id="适用范围-1"><a href="#适用范围-1" class="headerlink" title="适用范围"></a>适用范围</h4><p><span style="padding-left:2em;"></span>求问题的最优解。</p>
<h4 id="举例-1"><a href="#举例-1" class="headerlink" title="举例"></a>举例</h4><p><span style="padding-left:2em;"></span>给定一个9*9的格子地图，再给定初始状态和终止状态，输出从初始点到达终止点的最少步数。</p>
<h3 id="DFS-与-BFS-的比较"><a href="#DFS-与-BFS-的比较" class="headerlink" title="$DFS$与$BFS$的比较"></a>$DFS$与$BFS$的比较</h3><ul>
<li>数据结构：$DFS$采用栈，而$BFS$采用队列</li>
<li>算法思想：深度搜索与广度搜索的控制结构和产生系统很相似，唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点，所以在产生后继节点时可以去掉一部分重复的节点，从而提高了搜索效率。这两种算法每次都扩展一个节点的所有子节点，而不同的是，深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点</li>
<li>使用范围：$DFS$可以迅速的找到一个解，然后利用这个解进行剪枝，而$BFS$可找到最优解。</li>
</ul>
<h3 id="A-算法"><a href="#A-算法" class="headerlink" title="$A^{*}$算法"></a>$A^{*}$算法</h3><h4 id="算法思想-2"><a href="#算法思想-2" class="headerlink" title="算法思想"></a>算法思想</h4><p><span style="padding-left:2em;"></span>$DFS$和$BFS$在展开子结点时均属于盲目型搜索，也就是说，它不会选择哪个结点在下一次搜索中更优而去跳转到该结点进行下一步的搜索。在运气不好的情形中，均需要试探完整个解集空间, 显然，只能适用于问题规模不大的搜索问题中。<br><span style="padding-left:2em;"></span>$A^{*}$算法，作为启发式算法中很重要的一种，被广泛应用在最优路径求解和一些策略设计的问题中。<br>而$A^{*}$算法最为核心的部分，就在于它的一个估值函数的设计上：$$f(n)=g(n)+h(n)$$其中$f(n)$是每个可能试探点的估值，它有两部分组成：</p>
<ul>
<li>一部分，为$g(n)$，它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示）。</li>
<li>一部分，即$h(n)$，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值。</li>
</ul>
<p><span style="padding-left:2em;"></span>$h(n)$设计的好坏，直接影响着具有此种启发式函数的启发式算法的是否能称为$A^{*}$算法。<br>一种具有$f(n)=g(n)+h(n)$策略的启发式算法能成为$A^{*}$算法的充分条件是：</p>
<ol>
<li>搜索树上存在着从起始点到终了点的最优路径。</li>
<li>问题域是有限的。</li>
<li>所有结点的子结点的搜索代价值$&gt;0$。</li>
<li>满足$h(n)\leq h^{*}(n)$（$h^{*}(n)$为实际问题的代价值）。</li>
</ol>
<p><span style="padding-left:2em;"></span>当此四个条件都满足时，一个具有$f(n)=g(n)+h(n)$策略的启发式算法能成为$A^{*}$算法，并一定能找到最优解。<br><span style="padding-left:2em;"></span>对于一个搜索问题，显然，条件$1,2,3$都是很容易满足的，而条件$4:h(n)\leq h^{*}(n)$是需要精心设计的，由于$h^{*}(n)$显然是无法知道的，所以，一个满足条件$4$的启发策略$h(n)$就来的难能可贵了。<br><span style="padding-left:2em;"></span>不过，对于图的最优路径搜索问题，有些相关策略$h(n)$不仅很好理解，而且已经在理论上证明是满足条件$4$的，从而为这个算法的推广起到了决定性的作用。</p>
<h2 id="算法不足"><a href="#算法不足" class="headerlink" title="算法不足"></a>算法不足</h2><p><span style="padding-left:2em;"></span>与$BFS$相比，$DFS$的优点是比$BFS$需要较少的空间，它只需要保存搜索树的一部分，由当前正在搜索的路径和该路径上还没有完全展开的结点标识所组成。但是其主要问题是，它可能会搜索到了错误的路径上。很多问题可能具有很深甚至是无限的搜索树，如果不幸选择了一个错误的路径，那么$DFS$会一直搜索下去，而不会回到正确的路径上。这样对于这些问题，$DFS$要么陷入无限的循环，而不能给出一个答案，要么最后能够找到一个答案，但是路径很长，而且不是最优的答案。也就是说$DFS$既不是完备的，也不是最优的。</p>
<h2 id="算法改进"><a href="#算法改进" class="headerlink" title="算法改进"></a>算法改进</h2><h3 id="首次改进方法"><a href="#首次改进方法" class="headerlink" title="首次改进方法"></a>首次改进方法</h3><p><span style="padding-left:2em;"></span>对于搜索树的深度$d$比较大的情况，$DFS$需要很长的运行时间，而且还可能得不到答案。经过查阅资料，我找到了一种比较好的问题解决方案，就是对$d$进行控制，即有界深度优先搜索方法。有界$DFS$对$DFS$进行了一定改进，对搜索树的深度进行控制。有界$DFS$总体上按照$DFS$，在程序找到目标之前，通过迭代不断增大$d$以保证完备性和最优性。虽然会有不少重复搜索，但是鉴于每增加一次$d$，则搜索的时间复杂度会以指数级别增加，所以重复搜索的时间可以忽略，亦可以与$A^*$算法结合来剪枝。但它对搜索深度给出了一个深度限制$d_m$，当深度达到了$d_m$的时候，如果还没有找到解答，就停止对该分支的搜索，换到另外一个分支进行搜索。<br><span style="padding-left:2em;"></span>但是，对于有界$DFS$策略，仍然有以下几点需要说明：</p>
<ol>
<li>在有界$DFS$中，深度限制$d_m$是一个很重要的参数。当问题有解且解得路径长度小于等于$d_m$时候，则搜索过程一定能够找到解，但是和深度优先搜索一样，这并不能保证最先找到的是最优解。但是当$d_m$取的太小，解的路径长度大于$d_m$时，则搜索过程中就找不到解，即这时搜索过程甚至是不完备的。</li>
<li>深度限制$d_m$不能太大。当$d_m$太大时，搜索过程会产生过多的无用节点，既浪费了计算机资源，又降低了搜索效率。</li>
<li>有界深度搜索的主要问题是深度限制值$d_m$的选取。如果该值设置的比较合适，则会得到比较有效的有界$DFS$。但是对于很多问题我们并不知道该值到底是多少。为此可采用下面的二次改进方法：迭代机身搜索。<h3 id="二次改进方法"><a href="#二次改进方法" class="headerlink" title="二次改进方法"></a>二次改进方法</h3><span style="padding-left:2em;"></span>迭代加深搜索是一种会比选择最有深度限制问题的侧脸，是试图尝试所有可能的深度限制：首先深度为$0$，然后深度为$1$，然后为$2$，等等，一直进行下去。如果初始深度为$0$，则该算法只生成根节点，并检测它。如果根节点不是目标，则深度加$1$，通过典型的深度优先算法，生成深度为$1$的树。当深度限制为$m$时，树的深度为$m$。<br><span style="padding-left:2em;"></span>迭代加深搜索看起来会很浪费，因为很多节点都可能扩展多次。然而对于很多问题，这种多次的扩展负担实际上很小，直觉上可以想象，如果一棵树的分支系数很大，几乎所有的节点都在最底层上，则对于上面各层节点扩展多次对整个系统来说影响不是很大。最后，给出搜索最优策略的比较，作为证明：</li>
</ol>
<table>
<thead>
<tr>
<th>标准</th>
<th>宽度优先</th>
<th>深度优先</th>
<th>有界深度</th>
<th>迭代加深</th>
</tr>
</thead>
<tbody>
<tr>
<td>时间</td>
<td>$b^d$</td>
<td>$b^m$</td>
<td>$b^l$</td>
<td>$b^d$</td>
</tr>
<tr>
<td>空间</td>
<td>$b^d$</td>
<td>$bm$</td>
<td>$bl$</td>
<td>$bd$</td>
</tr>
<tr>
<td>最优</td>
<td>是</td>
<td>否</td>
<td>否</td>
<td>是</td>
</tr>
<tr>
<td>完备</td>
<td>是</td>
<td>否</td>
<td>如果$1&gt;d$，是</td>
<td>是</td>
</tr>
</tbody>
</table>
<blockquote>
<p>注：$b$是分支系数，$d$是解答的深度，$m$是搜索树的最大深度，$l$是深度限制。</p>
</blockquote>

      
    </div>
    
  </div>
  
	<! -- 添加打赏功能 -->
<div class ="post-donate">
    <div id="donate_board" class="donate_bar center">
        <a id="btn_donate" class="btn_donate" href="javascript:;" title="打赏">￥打赏</a><span class="donate_txt">赞助吃土少年！￣﹃￣</span>
    </div>  
	<div id="donate_guide" class="donate_bar center hidden" >
		<!-- 支付宝打赏图案 --><img src="/img/zhifubaodonate.png" alt="支付宝打赏" /> 
		<!-- 微信打赏图案 --><img src="/img/weixindonate.png" alt="微信打赏" />  
    </div>
	<script type="text/javascript">
		document.getElementById('btn_donate').onclick = function(){
			$('#donate_board').addClass('hidden');
			$('#donate_guide').removeClass('hidden');
		}
	</script>
</div>
  
  
    
    <div class="copyright">
        <p><span>本文标题:</span><a href="/2017/01/10/Algorithm-homework/">算法设计与分析——突破O(m)时间复杂度限制的无向图动态深度优先算法</a></p>
        <p><span>文章作者:</span><a href="/" title="回到主页">Shawn</a></p>
        <p><span>本文字数:</span><span class="post-count">6,355字</span></p>
        <p><span>发布时间:</span>2017-01-10, 14:30:48</p>
        <p><span>最后更新:</span>2017-01-27, 22:22:06</p>
        <p>
            <span>原始链接:</span><a class="post-url" href="/2017/01/10/Algorithm-homework/" title="算法设计与分析——突破O(m)时间复杂度限制的无向图动态深度优先算法">http://shawnzeng.com/2017/01/10/Algorithm-homework/</a>
            <span class="copy-path" data-clipboard-text="原文: http://shawnzeng.com/2017/01/10/Algorithm-homework/　　作者: Shawn" title="点击复制文章链接"><i class="fa fa-clipboard"></i></span>
            <script> var clipboard = new Clipboard('.copy-path'); </script>
        </p>
        <p>
            <span>许可协议:</span><i class="fa fa-creative-commons"></i> <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/" title="CC BY-NC-SA 4.0 International" target = "_blank">"署名-非商用-相同方式共享 4.0"</a> 转载请保留原文链接及作者。
        </p>
    </div>



    <nav id="article-nav">
        
            <div id="article-nav-newer" class="article-nav-title">
                <a href="/2017/01/13/PSPic/">
                    使用PS压缩背景图
                </a>
            </div>
        
        
            <div id="article-nav-older" class="article-nav-title">
                <a href="/2016/12/31/Hi2017/">
                    2017新年快乐！
                </a>
            </div>
        
    </nav>

  
  
</article>

    <div id="toc" class="toc-article">
        <strong class="toc-title">文章目录</strong>
        
            <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#论文概述"><span class="toc-number">1.</span> <span class="toc-text">论文概述</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#文章概要"><span class="toc-number">1.1.</span> <span class="toc-text">文章概要</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#问题定义及算法要求"><span class="toc-number">1.2.</span> <span class="toc-text">问题定义及算法要求</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#算法介绍"><span class="toc-number">1.3.</span> <span class="toc-text">算法介绍</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#准备工作"><span class="toc-number">1.3.1.</span> <span class="toc-text">准备工作</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#概述"><span class="toc-number">1.3.2.</span> <span class="toc-text">概述</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#不相交树分割法-Partition-T-U"><span class="toc-number">1.3.3.</span> <span class="toc-text">不相交树分割法$Partition(T,U)$</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#算法执行"><span class="toc-number">1.3.4.</span> <span class="toc-text">算法执行</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#静态-DFS-、动态-DFS-算法伪代码"><span class="toc-number">1.3.5.</span> <span class="toc-text">静态$DFS$、动态$DFS$算法伪代码</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#时间复杂度分析"><span class="toc-number">1.4.</span> <span class="toc-text">时间复杂度分析</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#论文综述"><span class="toc-number">2.</span> <span class="toc-text">论文综述</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#问题领域及分类"><span class="toc-number">2.1.</span> <span class="toc-text">问题领域及分类</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#深度优先算法-DFS"><span class="toc-number">2.2.</span> <span class="toc-text">深度优先算法($DFS$)</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#算法思想"><span class="toc-number">2.2.1.</span> <span class="toc-text">算法思想</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#适用范围"><span class="toc-number">2.2.2.</span> <span class="toc-text">适用范围</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#举例"><span class="toc-number">2.2.3.</span> <span class="toc-text">举例</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#广度优先算法-BFS"><span class="toc-number">2.3.</span> <span class="toc-text">广度优先算法($BFS$)</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#算法思想-1"><span class="toc-number">2.3.1.</span> <span class="toc-text">算法思想</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#适用范围-1"><span class="toc-number">2.3.2.</span> <span class="toc-text">适用范围</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#举例-1"><span class="toc-number">2.3.3.</span> <span class="toc-text">举例</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#DFS-与-BFS-的比较"><span class="toc-number">2.4.</span> <span class="toc-text">$DFS$与$BFS$的比较</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#A-算法"><span class="toc-number">2.5.</span> <span class="toc-text">$A^{*}$算法</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#算法思想-2"><span class="toc-number">2.5.1.</span> <span class="toc-text">算法思想</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#算法不足"><span class="toc-number">3.</span> <span class="toc-text">算法不足</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#算法改进"><span class="toc-number">4.</span> <span class="toc-text">算法改进</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#首次改进方法"><span class="toc-number">4.1.</span> <span class="toc-text">首次改进方法</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#二次改进方法"><span class="toc-number">4.2.</span> <span class="toc-text">二次改进方法</span></a></li></ol></li></ol>
        
    </div>
    <style>
        .left-col .switch-btn,
        .left-col .switch-area {
            display: none;
        }
        .toc-level-3 i,
        .toc-level-3 ol {
            display: none !important;
        }
    </style>

    <input type="button" id="tocButton" value="隐藏目录"  title="点击按钮隐藏或者显示文章目录">

    <script>
        yiliaConfig.toc = ["隐藏目录", "显示目录", !!"false"];
    </script>



    <div class="share">
    
        <div class="bdsharebuttonbox">
            <a href="#" class="fa fa-twitter bds_twi" data-cmd="twi" title="分享到推特"><span class=""></a>
            <a href="#" class="fa fa-weibo bds_tsina" data-cmd="tsina" title="分享到新浪微博"></a>
            <a href="#" class="fa fa-qq bds_sqq" data-cmd="sqq" title="分享给 QQ 好友"></a>
            <a href="#" class="fa fa-files-o bds_copy" data-cmd="copy" title="复制网址"></a>
            <a href="#" class="fa fa fa-envelope-o bds_mail" data-cmd="mail" title="通过邮件分享"></a>
            <a href="#" class="fa fa-weixin bds_weixin" data-cmd="weixin" title="生成文章二维码"></a>
            <a href="#" class="fa fa-share-alt bds_more" data-cmd="more"></i></a>
        </div>
       <script>
            window._bd_share_config={
                "common":{"bdSnsKey":{},"bdText":"算法设计与分析——突破O(m)时间复杂度限制的无向图动态深度优先算法　| 诗酒趁年华　","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='//bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];
        </script>
    

    
</div>







    
      <div class="duoshuo" id="comments">
    <div id="comment-box" ></div>
    <div class="ds-thread" id="ds-thread" data-thread-key="2017/01/10/Algorithm-homework/" data-title="算法设计与分析——突破O(m)时间复杂度限制的无向图动态深度优先算法" data-url="http://shawnzeng.com/2017/01/10/Algorithm-homework/"></div>
    <script type="text/javascript">
        var duoshuoQuery = {short_name:"zengshuai1996"};
        var loadComment = function(){
            var d = document, s = d.createElement('script');
            //s.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//shawnzeng.com/js/embed.js';
            s.src = '/js/embed.js';
            s.async = true; s.charset = 'UTF-8';
            (d.head || d.body).appendChild(s);
        }

        
    </script>
    
    <script> loadComment(); </script>

</div>
    




    <div class="scroll" id="post-nav-button">
        
            <a href="/2017/01/13/PSPic/" title="上一篇: 使用PS压缩背景图">
                <i class="fa fa-angle-left"></i>
            </a>
        

        <a title="文章列表"><i class="fa fa-bars"></i><i class="fa fa-times"></i></a>

        
            <a href="/2016/12/31/Hi2017/" title="下一篇: 2017新年快乐！">
                <i class="fa fa-angle-right"></i>
            </a>
        
    </div>

    <ul class="post-list"><li class="post-list-item"><a class="post-list-link" href="/2017/04/14/StopHexo/">停止更新</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/01/30/Https/">腾讯云Centos7启用https</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/01/25/AddBaiduCDN/">给自己的博客添加CDN加速</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/01/18/NightMode/">给自己的主题添加夜间模式</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/01/13/2017hanjiaplan/">2017寒假计划get√！</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/01/13/PSPic/">使用PS压缩背景图</a></li><li class="post-list-item"><a class="post-list-link" href="/2017/01/10/Algorithm-homework/">算法设计与分析——突破O(m)时间复杂度限制的无向图动态深度优先算法</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/31/Hi2017/">2017新年快乐！</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/30/HuaJi/">滑稽大盗</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/27/Serviceology02/">服务学作业——堆糖电商服务建模</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/14/Compile_SubsetConstruction_Algorithm/">编译原理——子集构造法</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/05/HexoStudy/">Hexo学习笔记</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/05/AddUML/">给hexo添加uml时序图和流程图功能</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/03/YourName/">「君の名は。」</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/12/01/Yoga/">林宥嘉：她说好</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/11/30/Compile02/">编译原理——语言及其文法</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/11/30/Compile01/">编译原理——简介</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/11/28/SDAPM-Scope-Statement/">Software Development And Project Management Homework——Scope Statement</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/11/28/SDAPM-Project-Charter/">Software Development And Project Management Homework——Project Charter</a></li><li class="post-list-item"><a class="post-list-link" href="/2016/11/05/RestartBlog/">重头再来:Mac上搭建基于GitHub的Hexo博客</a></li></ul>




    <script>
        
    </script>
</div>
      			<footer id="footer">
    <div class="outer">
        <div id="footer-info">
            <div class="footer-left">
                <i class="fa fa-copyright"></i> 
                2016-2017 <i class="fa fa-heart animated infinite pulse"></i> Shawn <a href="http://www.miitbeian.gov.cn">黑ICP备17000197号-1</a>
            </div>
            <div class="footer-right">
            	<span class="my-face">(●'◡'●)ﾉ</span>
				<span id="span_dt_dt"></span>
            </div>
        </div>
        
            <div class="visit">
                
                    <span id="busuanzi_container_site_pv" style='display:none'>
                        <span id="site-visit" title="本站到访数"><i class="fa fa-user" aria-hidden="true"></i><span id="busuanzi_value_site_uv"></span>
                        </span>
                    </span>
                
                
                    <span>| </span>
                
                
                    <span id="busuanzi_container_page_pv" style='display:none'>
                        <span id="page-visit"  title="本页阅读量"><i class="fa fa-eye animated infinite pulse" aria-hidden="true"></i><span id="busuanzi_value_page_pv"></span>
                        </span>
                    </span>
                
            </div>
        
    </div>
</footer>

    		</div>
    		<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script>


    <script src="/js/raphael.js"></script>
    <script src="/js/underscore.js"></script>
    <script src="/js/sequence-diagram.js"></script>
    <script src="/js/flowchart.js"></script>
    
<!-- Chart Render -->
<script type="text/javascript">
  $(".sequence").sequenceDiagram({theme: 'simple'});
  var flowCount = 0;
  $(".flow").each(function() {
      var el = $(this);
      el.hide();
      el.after('<div id="flow-' + flowCount + '"></div>');
      var chart = flowchart.parse(el.text());
      chart.drawSVG('flow-' + flowCount);
      flowCount++;
  });
</script>
<!-- End Chart Render -->


<script data-main="/js/main.js" src="//cdn.bootcss.com/require.js/2.2.0/require.min.js"></script>

    <script>
        $(document).ready(function() {
            var iPad = window.navigator.userAgent.indexOf('iPad');
            if (iPad > -1 || $(".left-col").css("display") === "none") {
                var bgColorList = ["#9db3f4", "#414141", "#e5a859", "#f5dfc6", "#c084a0", "#847e72", "#cd8390", "#996731"];
                var bgColor = Math.ceil(Math.random() * (bgColorList.length - 1));
                $("body").css({"background-color": bgColorList[bgColor], "background-size": "cover"});
            }
            else {
                var backgroundnum = 5;
                var backgroundimg = "url(/background/bg-x.jpg)".replace(/x/gi, Math.ceil(Math.random() * backgroundnum));
                $("body").css({"background": backgroundimg, "background-attachment": "fixed", "background-size": "cover"});
            }
        })
    </script>





    <script type="text/x-mathjax-config">
MathJax.Hub.Config({
  tex2jax: {
    inlineMath: [['$','$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code'],
	linebreaks: { automatic: true, width: "container" }
  }
});

MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for(i=0; i < all.length; i += 1) {
        all[i].SourceElement().parentNode.className += ' has-jax';                 
    }       
});
</script>

<!--script type="text/javascript" src="http://mathjax.josephjctang.com/MathJax.js?config=TeX-MML-AM_HTMLorMML"-->
<!--script type="text/javascript" src="//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"-->
<script type="text/javascript" src="//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-MML-AM_HTMLorMML">
</script>


<div class="scroll" id="scroll">
    <a href="#" title="返回顶部"><i class="fa fa-arrow-up"></i></a>
    <a href="#comments" onclick="load$hide();" title="查看评论"><i class="fa fa-comments-o"></i></a>
    <a href="#footer" title="转到底部"><i class="fa fa-arrow-down"></i></a>
</div>
<script>
    // Open in New Window
    
        var oOpenInNew = {
            
            
            
            
            
            
            
             miniArchives: "a.post-list-link", 
            
             friends: "#js-friends a", 
             socail: ".social a" 
        }
        for (var x in oOpenInNew) {
            $(oOpenInNew[x]).attr("target", "_blank");
        }
    
</script>

    <script>
        var originTitle = document.title;
        var titleTime;
        document.addEventListener("visibilitychange", function() {
            if (document.hidden) {
                document.title = "(つェ⊂)" + originTitle;
                clearTimeout(titleTime);
            }
            else {
                document.title = "(*´∇｀*)" + originTitle;
                titleTime = setTimeout(function() {
                    document.title = originTitle;
                }, 2000);
            }
        })
    </script>

<script async src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    		<div class="musicbox">
				<div class="player">
					<div id="player_bck" class="aplayer"></div>
				</div>
				<div class="pop-music" title="音乐"></div>
			</div>
  		</div>
  		<script src="/js/music.js"></script>
	</body>	
</html>